Strategic behavior when allocating indivisible goods sequentially

Title: Strategic behavior when allocating indivisible goods sequentially
Creator: Kalinowski, Thomas; Narodytska, Nina; Walsh, Toby; Xia, Lirong
Relation: The 27th AAAI Conference (AAAI 2013). Proceedings of the 27th AAAI Conference (Bellevue, WA 14-18 July, 2013) p. 452-458
Relation: http://www.aaai.org/Conferences/AAAI/aaai13.php
Publisher: AAAI Press
Resource Type: conference paper
Date: 2013
Description: We study a simple sequential allocation mechanism for allocating indivisible goods between agents in which agents take turns to pick items. We focus on agents behaving strategically. We view the allocation procedure as a finite repeated game with perfect information. We show that with just two agents, we can compute the unique sub-game perfect Nash equilibrium in linear time. With more agents, computing the sub-game perfect Nash equilibria is more difficult. There can be an exponential number of equilibria and computing even one of them is PSPACE-hard. We identify a special case, when agents value many of the items identically, where we can efficiently compute the subgame perfect Nash equilibria. We also consider the effect of externalities and modifications to the mechanism that make it strategy proof.
Subject: sequential allocation mechanism; division; Nash equilibrium
Identifier: http://hdl.handle.net/1959.13/1301220
Identifier: uon:20238
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format